//
//  singlyLinkedList.c
//  Chapter_1
//
//  Created by hao on 18/3/18.
//  Copyright © 2018年 hao. All rights reserved.
//

// 单向链表的增删查改
#include "singlyLinkedList.h"

// 创建一个空链表
SinglyList makeSinglyList()
{
    SinglyList list = (SinglyList)malloc(sizeof(struct SinglyLinkedNode));
    return list;
}

// 返回第k个位置链表的data
SinglyList findKthInSinglyList(int k, SinglyList list)
{
    SinglyList ptrl = list;
    int i = 1;
    while (ptrl != TPL_LIST_NULL && i < k) {
        i++;
        ptrl = ptrl->next;
    }
    if (i == k) {
        return ptrl;
    }
    return TPL_LIST_NULL;
}

// 在线性表中查找第一次出现 x 的值的位置
SinglyList findElemInSinglyList(ElementType x, SinglyList list)
{
    SinglyList ptrl = list;
    while (ptrl != TPL_LIST_NULL) {
        if (ptrl->data == x) {
            break ;
        }
        ptrl = ptrl->next;
    }
    return ptrl;
}

// 在序列 i 前插入一个新元素 x
SinglyList insertInSinglyList(ElementType x, int i, SinglyList list)
{
    SinglyList insertL = makeSinglyList();
    insertL->data = x;
    // 表示插入到第一个节点
    if (i == 1) {
        insertL->next = list;
        return insertL;
    }
    // 查找出来的还是指向list的链表指针
    SinglyList ptrl = findKthInSinglyList(i-1, list);
    if (ptrl == TPL_LIST_NULL) {
        printf("插入位置不正确");
    } else {
        insertL->next = ptrl->next;
        ptrl->next = insertL;
    }
    return list;
}

// 删除指定位置 i 的元素
SinglyList deleteElemInSinglyList(int i, SinglyList list)
{
    SinglyList ptrl, s;
    if (i == 1) {
        s = list; // 拿到首地址
        if (list == TPL_LIST_NULL) {
            return TPL_LIST_NULL;
        }
        // 将list首地址指向next
        list = list->next;
        // 释放开始拿到的首地址
        free(s);
        s = TPL_LIST_NULL;
        return list;
    }
    ptrl = findKthInSinglyList(i-1, list);
    if (ptrl == TPL_LIST_NULL) {
        printf("第%d个节点不存在", i-1);
        return TPL_LIST_NULL;
    } else if (ptrl->next == TPL_LIST_NULL) {
        printf("第%d个节点不存在", i);
        return TPL_LIST_NULL;
    } else {
        s = ptrl->next;
        ptrl->next = s->next;
        free(s);
        s = TPL_LIST_NULL;
    }
    return list;
}

// 返回单向链表的长度
int singlyListLength(SinglyList list)
{
    int i = TPL_LIST_EMPTY;
    SinglyList p = list;
//    printf("next is %d \n", p == NULL);
    while (p != TPL_LIST_NULL) {
//        printf("next is %d address = %p \n", p == NULL, p);
        p = p->next;
        i++;
    }
    return i;
}

// 将链表的值打印出来
void printfSinglyList(SinglyList list)
{
    printf("start:");
    while (list != TPL_LIST_NULL) {
        printf("%d\t", list->data);
        list = list->next;
    }
    printf("end: \n");
}
